package io.github.consoles.dsa;

/**
 * http://www.cnblogs.com/ikesnowy/p/7157826.html
 * Created by yiihua-013 on 17/8/30.
 * <p>
 * 栈的可生成性。
 * 假设我们的栈测试用例会进行一系列的入栈和出栈操作，
 * 序列中的整数 0, 1, ... , N - 1 （按此先后顺序排列）表示入栈操作，N个减号表示出栈操作。
 * 设计一个算法，判定给定的混合序列是否会使数组向下溢出
 * （你使用的空间量与 N 无关，即不能用某种数据结构存储所有整数）。
 * 设计一个线性时间算法判定我们的测试用例能否产生某个给定的排列
 * （这取决于出栈操作指令的出现位置）。
 * <p>
 * 对于某个整数k,除非前k次出栈操作会在前k次入栈操作前完成,否则栈不会向下溢出
 * <p>
 * 如果某个序列可以产生,那么产生它的方式将是唯一的:如果输出序列中的下一个整数在栈顶将其弹出,否则压入栈中
 * <p>
 * 栈的可生成性问题中禁止出现的排列。
 * 若三元组 (a, b, c) 中 a<b<c 且 c 最先被弹出，a 第二，b 第三
 * （c 和 a 以及 a 和 b 之间可以间隔其他整数）
 * <p>
 * 首先有结论：对于栈顶元素 Sn，栈中所有小于 Sn 的值都以递减形式保存（已经输出的不算）。
 * 表现在输出序列中，Sn 输出之后，如果有小于 Sn 的值输出，其顺序必定是递减的。
 * 例如序列 4 3 2 1 0 9 8 7 6 5
 * 4 输出之后，3 2 1 0 递减输出；9 输出之后，8 7 6 5 递减输出。
 * 依次验证其中的每个值都能满足结论。
 * 而对于序列 4 6 8 7 5 3 2 9 0 1
 * 对于 4，之后的 3 2 1 0 并不是以递减顺序输出的，因此这个序列是不合法的。
 */
public class StackUtil {

    /**
     * 记录栈中元素数量，如果元素数量小于 0 则会出现下溢出。
     *
     * @param seq
     * @return
     */
    public boolean isUnderflow(String seq) {
        String[] split = seq.split(" ");
        int count = 0;
        for (String c : split) {
            if (c.equals("-")) {
                count--;
            } else {
                count++;
            }
            if (count < 0) return true;
        }
        return false;
    }

    public boolean isRightSeq(int[] seq) {
        LinkedStack<Integer> stack = new LinkedStack<>();

        int input = 0; // 自然数0,1,2,3输入序列
        int len = seq.length;

        for (int i : seq) {
            // 如果栈为空，则从输入序列中压入一个数。
            if (stack.isEmpty()) {
                stack.push(input++);
            }
            // 如果输出序列的下一个数不等于栈顶的数，那么就从输入序列中压入一个数。
            // 加入input < len的限制主要是不合法序列可能导致死循环
            while (stack.peek() != i && input < len) {
                System.out.println("->" + input);
                stack.push(input++);
            }
            // 如果栈顶的数等于输出的数，弹出它。
            if (stack.peek() == i) {
                System.out.println("<-" + stack.pop());
            }
        }
        return stack.isEmpty();
    }
}
